# This function computes the set of conjugates of &alpha;`^n,
# the*GF*G)
compConjugates := proc (G, p, m, n)
local a, an, k, conjugate, conjugates, powers;
    a := G:-ConvertIn(alpha);
    an := G:-`^`(a, n);
    conjugates := [an];
    k := 1;
    powers := [n];
    conjugate := G:-`^`(an, p);
    while an <> conjugate do conjugates := [op(conjugates), conjugate];
        powers := [op(powers), `mod`(n*p^k, p^m-1)];
        k := k+1;
        conjugate := G:-`^`(an, p^k)
    end do;
    powers
end proc:

# called by minpol
compMinPolynomial := proc (p, n, pol, C) local q, m, d, a;
    q := p^n-1;
    a := RootOf(pol);
    m := 1;
    for d in C do m := m*(x+a^d) end do;
    `mod`(Expand(m), p)
end proc:

# This function computes the minimal polynomial for the member
# alpha`^n*of*the*Galois*Field*GF(p^m)
minpol := proc (p, m, pol, n) local G, C;
    G := GF(p, m, pol);
    C := compConjugates(G, p, m, n);
    compMinPolynomial(p, m, pol, C)
end proc:

# This function computes the generator matrix of the BCH code which
# corrects t errors and has length (p^m -1). A codeword is in
# GF(p⋅⋅m)corrects t errors and has length (p^m -1). A codeword is in
# GF(p⋅⋅m) realized by the polynomial pol.
compBCHGenPol := proc (t, p, m, pol) local length, minpols, i;
    length := p^m-1;
    minpols := 1;
    for i by 2 to 2*t-1 do
        minpols := minpols*minpol(p, m, pol, i)
    end do;
    `mod`(Expand(minpols), p)
end proc:

# This function computes both the generator and parity check
# polynomials of BCH codes.
compGH := proc (t, p, m, pol) local g, h;
    g := compBCHGenPol(t, p, m, pol);
    h := `mod`(quo(x^(p^m-1), g, x), p);
    [g, h]
end proc:

g := compBCHGenPol(3, 2, 4, alpha^4+alpha+1, 1);

L := compGH(3, 2, 4, alpha^4+alpha+1, 1);

# Computes the message polynomial from its list representation.
toPol := proc (msg) local i, result;
    result := 0;
    for i to nops(msg) do
        result := result+msg[i]*x^(i-1)
    end do;
    result
end proc:

toPol([1, 0, 1]);

# converts a polynomial of a message to its bit-list representation.
toMsg := proc (p) local d, msg, i;
    msg := [coeff(p, x, 0)];
    for i to degree(p) do
        msg := [op(msg), coeff(p, x, i)]
    end do;
    msg
end proc:

# This function implements the encoder for BCH codes.
encode := proc (msg, t, p, m, pol) local g, c;
    g := compBCHGenPol(t, p, m, pol);
    c := `mod`(Expand(toPol(msg)*g), p);
    toMsg(c)
end proc:


